{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Recursive Mulitply LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: multiply"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #递归乘法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。</p>\n",
    "\n",
    "<p> <strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：A = 1, B = 10\n",
    "<strong> 输出</strong>：10\n",
    "</pre>\n",
    "\n",
    "<p> <strong>示例2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：A = 3, B = 4\n",
    "<strong> 输出</strong>：12\n",
    "</pre>\n",
    "\n",
    "<p> <strong>提示:</strong></p>\n",
    "\n",
    "<ol>\n",
    "<li>保证乘法范围不会溢出</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [recursive-mulitply-lcci](https://leetcode.cn/problems/recursive-mulitply-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [recursive-mulitply-lcci](https://leetcode.cn/problems/recursive-mulitply-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        tags = [True] * (n)\n",
    "        for i in range(len(tags)):\n",
    "            if i == 0 or i == 1 or not tags[i]:\n",
    "                tags[i] = False\n",
    "            elif tags[i]:\n",
    "                multiply = 2\n",
    "                while i * multiply < n:\n",
    "                    tags[i * multiply] = False\n",
    "                    multiply += 1\n",
    "        return len([item for item in tags if item])\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        c = 0\n",
    "        while A:\n",
    "            if A&1:\n",
    "                c += (A&1)*B\n",
    "            A >>= 1\n",
    "            B <<= 1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B == 0: return 0\n",
    "        return A + self.multiply(A, B - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(B):\n",
    "            res += A\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        # 递归\n",
    "        if A>B:\n",
    "            A,B = B,A\n",
    "        if A==0:return 0\n",
    "        return B+self.multiply(A-1,B)\n",
    "        \n",
    "        # if A>B:\n",
    "        #     A,B = B,A\n",
    "        # res ,acc = 0, B\n",
    "        # while A:\n",
    "        #     if A&1==0:\n",
    "        #         acc<<=1\n",
    "        #     res+=acc\n",
    "        #     A>>=1\n",
    "        # return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        # 递归\n",
    "        # if A>B:\n",
    "        #     A,B = B,A\n",
    "        # if A==0:return 0\n",
    "        # return B+self.multiply(A-1,B)\n",
    "        \n",
    "        if A>B:\n",
    "            A,B = B,A\n",
    "        res ,acc = 0, B\n",
    "        while A:\n",
    "            if A&1:\n",
    "                res+=acc\n",
    "            acc<<=1\n",
    "            A>>=1\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        # 递归\n",
    "        # if A>B:\n",
    "        #     A,B = B,A\n",
    "        # if A==0:return 0\n",
    "        # return B+self.multiply(A-1,B)\n",
    "        \n",
    "        if A>B:\n",
    "            A,B = B,A\n",
    "        res ,acc = 0, B\n",
    "        while A:\n",
    "            if A&1:\n",
    "                res+=acc\n",
    "            acc<<=1\n",
    "            A>>=1\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        ax = max(A,B)\n",
    "        im = min(A,B)\n",
    "        res = 0\n",
    "        for _ in range(im):\n",
    "            res += ax\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B == 0:\n",
    "            return 0\n",
    "        return A + self.multiply(A, B - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A < B:\n",
    "            return self.multiply(B, A)\n",
    "        if B == 1: return A\n",
    "        if B % 2 == 1:\n",
    "            return A + self.multiply(A, B//2) * 2\n",
    "        return self.multiply(A, B//2) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B == 0:\n",
    "            return 0\n",
    "        return A + self.multiply(A, B - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        result=0\n",
    "        while A!=0:\n",
    "            if A%2!=0:\n",
    "                result=result+B\n",
    "            A>>=1\n",
    "            B<<=1\n",
    "        return result        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        mul = 0\n",
    "        for i in range (B) :\n",
    "            mul = mul + A\n",
    "\n",
    "        return mul"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        toadd = 0\n",
    "        while(B>1):\n",
    "            if B%2==0:\n",
    "                A = A << 1\n",
    "                B = B >> 1\n",
    "            else:\n",
    "                B = B - 1\n",
    "                toadd += A\n",
    "        return A + toadd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B==1:\n",
    "            return A\n",
    "        return A+self.multiply(A,B-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        def R(a, b, res, base):\n",
    "            if b == 0:\n",
    "                return res\n",
    "            else:\n",
    "                print((base * (b % 2)),(a << base) * (b % 2))\n",
    "                return R(a, b >> 1, res + ((a << base) * (b % 2)), base + 1)\n",
    "\n",
    "        return R(A, B, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A == 0:\n",
    "            return 0\n",
    "        p = self.multiply(A >> 1, B)\n",
    "        if A%2:\n",
    "            return B+p+p\n",
    "        return p+p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        c=0\n",
    "        for _ in range(B):\n",
    "            c+=A\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        def recursion(x, y):\n",
    "            if y == 1:\n",
    "                return x\n",
    "            else:\n",
    "                mod = y % 2\n",
    "                y >>= 1\n",
    "                return recursion(x, y) + recursion(x, y) if mod == 0 else recursion(x, y) + recursion(x, y) + x\n",
    "        \n",
    "        ans = recursion(A, B)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B == 1:\n",
    "            return A\n",
    "        elif B % 2 == 0:\n",
    "            return self.multiply(A + A, B // 2)\n",
    "        else:\n",
    "            return A + self.multiply(A, B - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A * B\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B>A:\n",
    "            A,B=B,A\n",
    "        outnum=0\n",
    "\n",
    "        i=0\n",
    "        while B!=0:\n",
    "            if B&1==1:\n",
    "                outnum+=A<<i\n",
    "            B>>=1\n",
    "            i+=1\n",
    "\n",
    "        return outnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B\n",
    "        ans = 0 \n",
    "        if A == 0: return 0\n",
    "        elif A == 1: return B\n",
    "        else: \n",
    "            ans = self.multiply(A//2, B)\n",
    "            if A%2==0:\n",
    "                return ans + ans \n",
    "            else: \n",
    "                return B + ans + ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A * B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A==0 or B==0: return 0\n",
    "        if A>B:A, B=B, A\n",
    "        p=self.multiply(A//2,B)\n",
    "        if A%2: return p+p+B\n",
    "        else: return p+p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A>B:\n",
    "            temp = A\n",
    "            A = B\n",
    "            B = temp\n",
    "        if A==1:\n",
    "            return B\n",
    "        else:\n",
    "            return self.multiply(A-1,B)+B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A == 0 or B == 0:\n",
    "            return 0\n",
    "        \n",
    "        if A == 1:\n",
    "            return B\n",
    "        if B == 1:\n",
    "            return A\n",
    "\n",
    "        if A < B:\n",
    "            return B + self.multiply(A-1, B)\n",
    "        else:\n",
    "            return A + self.multiply(A, B-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        Max = max(A, B)\n",
    "        Min = min(A, B)\n",
    "        if Min == 0:\n",
    "            return 0\n",
    "        return self.multiply(Min - 1, Max) + Max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B == 1:\n",
    "            return A\n",
    "        elif B % 2 == 0:\n",
    "            return self.multiply(A + A, B >> 1)\n",
    "        else:\n",
    "            return A + self.multiply(A, B - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B>A:\n",
    "            A,B=B,A\n",
    "         \n",
    "        def my_multiply(a,b):\n",
    "            if b==0:\n",
    "                return 0\n",
    "\n",
    "            # if b%2==0:\n",
    "            if b&1==0:\n",
    "                return my_multiply(a<<1,b>>1)\n",
    "            else:\n",
    "                return a+my_multiply(a,b-1)\n",
    "\n",
    "        return my_multiply(A,B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B==0:\n",
    "            return 0\n",
    "        else:\n",
    "            return A+self.multiply(A,B-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        a=A\n",
    "        for i in range(1,B):\n",
    "          a=A+a\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A == 0 or B == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return A + self.multiply(A ,B-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        res = 0\n",
    "        # 判断A和B谁大，递归小的哪一个\n",
    "        if A>B:\n",
    "            A,B = B,A\n",
    "\n",
    "        def backtrack():\n",
    "            nonlocal res,A\n",
    "\n",
    "            if A==0:\n",
    "                return\n",
    "            res +=B\n",
    "            A-=1\n",
    "            backtrack()\n",
    "            \n",
    "\n",
    "        backtrack()\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A>B:\n",
    "            temp = A\n",
    "            A = B\n",
    "            B = temp\n",
    "        if A==1:\n",
    "            return B\n",
    "        else:\n",
    "            return self.multiply(A-1,B)+B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        def add(num,n,sum):\n",
    "            if n==0:\n",
    "                return sum\n",
    "            return add(num,n-1,sum+num)\n",
    "        if A<B:\n",
    "            return add(B,A,0)\n",
    "        else:\n",
    "            return add(A,B,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        m=A if A>=B else B\n",
    "        n=B if A>=B else A\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans+=m\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        \n",
    "        ans = 0 \n",
    "        if A == 0: return 0\n",
    "        elif A == 1: return B\n",
    "        else: \n",
    "            half = A>>1\n",
    "            ans = self.multiply(half, B)\n",
    "            if A - half - half ==0:\n",
    "                return ans + ans \n",
    "            else: \n",
    "                return B + ans + ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B==0:\n",
    "            return 0\n",
    "        product= A+ self.multiply(A,B-1)\n",
    "        return product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B == 1:\n",
    "            return A\n",
    "        # print(A, B)\n",
    "        C = self.multiply(A, B>>1) + self.multiply(A, B>>1)\n",
    "        if B&1 != 0:\n",
    "            # 奇数\n",
    "            C += A\n",
    "        return C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        count=0\n",
    "\n",
    "        while B!=0:\n",
    "            if B&1!=0:\n",
    "                count+=A\n",
    "            B>>=1\n",
    "            A<<=1\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        def f(a,b):\n",
    "            if a==1:\n",
    "                return b\n",
    "            return f(a-1,b)+b\n",
    "        if A>B:\n",
    "            t = A\n",
    "            A = B\n",
    "            B = t\n",
    "        return f(A,B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A == 0 or B == 0:\n",
    "            return 0\n",
    "        if B == 1:\n",
    "            return A\n",
    "        return A+self.multiply(A, B-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A==0:\n",
    "            return 0\n",
    "        p = self.multiply(A >> 1,B)\n",
    "        if A & 1:\n",
    "            return B+(p << 1 )\n",
    "        return p << 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B == 0:\n",
    "            return 0\n",
    "        return A + self.multiply(A, B - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return self.chengfa(A,B)\n",
    "        \n",
    "    def  chengfa(self,a,b):\n",
    "        if b == 0:\n",
    "            return 0\n",
    "        return a + self.chengfa(a,b-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A==0:\n",
    "            return 0\n",
    "        p = self.multiply(A >> 1,B)\n",
    "        if A %2 ==1:\n",
    "            return B+(p << 1 )\n",
    "        return p + p\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A > B:\n",
    "            A, B = B, A\n",
    "        if A == 1:\n",
    "            return B\n",
    "        ret = B + self.multiply(A-1, B) \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        count = 1\n",
    "        temp = A\n",
    "        temp_product = [[count, temp]]\n",
    "        while count <= B:\n",
    "            temp += temp\n",
    "            count += count\n",
    "            temp_product.append([count, temp])\n",
    "        result = 0\n",
    "        for i in range(len(temp_product) - 1, -1, -1):\n",
    "            if B >= temp_product[i][0]:\n",
    "                result += temp_product[i][1]\n",
    "                B -= temp_product[i][0]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        def dfs(A, B):\n",
    "            if B == 1:\n",
    "                return A\n",
    "            return dfs(A, B >> 1) << 1 if B & 1 == 0 else A + (dfs(A, B >> 1) << 1)\n",
    "        return dfs(A, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A==0:\n",
    "            return 0\n",
    "        p = self.multiply(A >> 1,B)\n",
    "        if A %2 ==1:\n",
    "            return B+(p << 1 )\n",
    "        return p << 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A * B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        def multi(a, b):\n",
    "            if b==0:\n",
    "                return 0\n",
    "            return a + multi(a, b-1)\n",
    "        if A > 0 and B > 0:\n",
    "            return multi(A, B)\n",
    "        if A < 0 and B < 0:\n",
    "            return multi(-A, -B)\n",
    "        if A > 0 and B < 0:\n",
    "            return -multi(A, -B)\n",
    "        if A < 0 and B > 0:\n",
    "            return -multi(-A, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if A == 0 or B == 0:\n",
    "            return 0\n",
    "        \n",
    "        if A == 1:\n",
    "            return B\n",
    "        if B == 1:\n",
    "            return A\n",
    "\n",
    "        if A < B:\n",
    "            return B + self.multiply(A-1, B)\n",
    "        else:\n",
    "            return A + self.multiply(A, B-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        while B == 1:\n",
    "            return A\n",
    "        return A + self.multiply(A, B-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        if B == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return A + self.multiply(A,B-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        y=0\n",
    "        while True:\n",
    "            if B == 1:\n",
    "                return A\n",
    "                break\n",
    "            j = B//2\n",
    "            if B%2 == 1:\n",
    "                y=y+A\n",
    "            A = A + A\n",
    "            B = j\n",
    "            if B == 1:\n",
    "                break\n",
    "        return y+A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        ans = 0 \n",
    "        if A == 0: return 0\n",
    "        elif A == 1: return B\n",
    "        else: \n",
    "            ans = self.multiply(A//2, B)\n",
    "            if A%2==0:\n",
    "                return ans + ans \n",
    "            else: \n",
    "                return B + ans + ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: int, B: int) -> int:\n",
    "        return A*B"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
